package leetcode_61_80;

public class uniquePathsWithObstacles_63 {
    /**
     * 一个机器人位于一个 m x n 网格的左上角
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角
     *网格中有障碍物。计算从左上角到右下角将会有的路径
     * 网格中的障碍物和空位置分别用 1 和 0 来表示。
     *
     * 0ms  100%，小开心
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        /**
        依然是动态规划,
        在障碍物所在位置直接赋值0
         */
        int row=obstacleGrid.length,col=obstacleGrid[0].length;
        int [][] dp=new int[row][col];
        //初始化最后一行最后一列，这些格子到达终点都只有一种路径，
        for(int i=row-1;i>=0;i--){           //倒着赋值方便操作
            if(obstacleGrid[i][col-1]==1) //遇到障碍物，前面的格子必然无法到达
                break;
            dp[i][col-1]=1;
        }
        for(int i=col-1;i>=0;i--){
            if(obstacleGrid[row-1][i]==1)
                break;
            dp[row-1][i]=1;
        }
        for(int i=row-2;i>=0;i--){   //行
            for(int t=col-2;t>=0;t--){  //列
                if(obstacleGrid[i][t]==1) //遇到障碍物,不赋值
                    continue;
                dp[i][t]=dp[i+1][t]+dp[i][t+1]; //每次只能向下或者向右移动一步
            }
        }
        return dp[0][0];
    }
}
